package datastructure.tree;

import java.util.Stack;

/**
 * Deep first search for a binary tree
 * 
 * @author Lei
 */
public class DeepFirstSearch {

    public static boolean search(TreeNode node, int value) {

        // Check if it's an empty tree.
        if (node == null) {
            return false;
        }

        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(node);

        while (!stack.isEmpty()) {

            TreeNode currentNode = stack.pop();
            if (currentNode.value == value) {
                // Found the value!
                return true;
            }

            if (currentNode.right != null) {
                stack.push(currentNode.right);
            }

            // As we want to visit left child first, we must push this node last
            if (currentNode.left != null) {
                stack.push(currentNode.left);
            }
        }

        // Not found.
        return false;
    }
}
